import random


class Node:
    def __init__(self, val):
        self.next = None
        self.prev = None
        self.below = None
        self.above = None
        self.val = val


class Skiplist:
    def __init__(self):
        self.head = Node(-1)
        self.maxLevel = 7
        for i in range(self.maxLevel + 1):
            level = Node(-1)
            level.below = self.head
            self.head.above = level
            self.head = level

    def search(self, target: int) -> bool:
        node = self.__search(target)
        return node.val == target

    def add(self, num: int) -> None:
        cursor = self.__search(num)
        node = Node(num)
        nextNode = cursor.next
        cursor.next = node
        node.prev = cursor
        node.next = nextNode
        if nextNode:
            nextNode.prev = node
        i = 0
        while i < self.maxLevel and random.randint(1, 2) == 2:
            level = Node(num)
            node.above = level
            level.below = node
            prevNode = node.prev
            while prevNode and prevNode.above is None:
                prevNode = prevNode.prev
            aboveNode = prevNode.above
            nextAboveNode = aboveNode.next
            aboveNode.next = level
            level.prev = aboveNode
            level.next = nextAboveNode
            if nextAboveNode:
                nextAboveNode.prev = level
            node = level
            i += 1

    def erase(self, num: int) -> bool:
        cursor = self.__search(num)
        if cursor.val != num:
            return False
        while cursor:
            prevNode = cursor.prev
            nextNode = cursor.next
            prevNode.next = nextNode
            if nextNode:
                nextNode.prev = prevNode
            cursor = cursor.above
        return True

    def __search(self, target):
        p = self.head
        while p.below:
            p = p.below
            while p.next and target >= p.next.val:
                p = p.next

        return p
